/*
对于给定的整数 n, 如果n的k（k>=2）进制数的所有数位全为1，则称 k（k>=2）是 n 的一个好进制。

以字符串的形式给出 n, 以字符串的形式返回 n 的最小好进制。

提示：

n的取值范围是 [3, 10^18]。
输入总是有效且没有前导 0。
 
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/smallest-good-base
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

#include <string>
using namespace std;
class Solution
{
public:
    string smallestGoodBase(string n)
    {
        // k^m <  n = 1 + k + k^2 + ... + k^m = (k^(m+1) - 1) / (k - 1) < k^(m+1)
        long nVal = stol(n);
        int mMax = floor(log(nVal) / log(2)); // m < log_k(n) < m + 1
        for (int m = mMax; m > 1; m--)
        {
            // (k+1)^m = 1 + m*k + ... + k^m > 1 + k + k^2 + ... + k^m = n > k^m
            // k+1 > n^(1/m) > k
            int k = pow(nVal, 1.0 / m);
            long mul = 1, sum = 1;
            for (int i = 0; i < m; i++)
            {
                mul *= k;
                sum += mul;
            }
            if (sum == nVal)
            {
                return to_string(k);
            }
        }
        return to_string(nVal - 1);
    }
};